In the transmission of digital data, streams of data bits are frequently subject to noise and like environmental impact which degrades the transmission at the point of its receipt, with resulting loss of some of the transmitted message. The art has long looked to various measures for transmitting the message data with error-correction data, such that the message data may be reconstructed in the receiver and noise-impacted message data may be recovered.
One measure for error-correction employs redundant codes of convolutional type. At the point of encoding the message data for transmission, plural digits (code symbols) are created for each digit of the message data. In creating the code symbols, the choice of symbols selected to represent an input digit of the message data is affected not only by the input digit itself, but also by preceding digits of the message data. Given such order, reconstruction is enabled in the receiver.
This practice gives rise to data "states" in the transmitted and received messages, i.e., a code situation in which each possible sequence of future data immediately following that state is decoded in a particular predetermined manner. FIG. 1 herein is taken from U.S. Pat. No. 3,789,360 and shows a "tree" of possible code data sequences for a short segment of convolutional code having a rate of two, i.e., two code symbols are generated for each digit of message data. In this tree, a path is followed dependently on the value of message digits. From any node, an upper path is taken when the message digit being encoded is zero and a lower path is taken when the message digit being encoded is one.
Four states are identified in FIG. 1 by the numerals in the square boxes at the tree nodes. For each state, rightward progress from any node correspondingly numbered is the same. Predictable in accordance with the code of the FIG. 1 tree, are the two ways in which each state can be entered and the two ways in which the state can be left. The transition from one state to another, as by the encoding of a succeeding message digit is termed a "branch interval". "State metrics" are derivable for each state and "branch metrics" are derivable for each branch interval.
A "trellis" is typically constructed, identifying the possible data sequences in terms of data states. From the trellis, "survivor sequences" or paths are determinable and correlations are computed for selecting the paths which are to survive. A circuit implementation of a trellis connection computer is shown in FIG. 6 of the '360 patent. The functions implemented in such computer involve an initial processing simultaneously in four correlators of the latest received branch data with a data pattern which each correlator is prewired to represent, i.e., one of the four possible state values (00, 11, 01 and 10). The result of each correlation (branch metric) is applied to a pair of adders, one for each of the two states which can be entered by means of convolution data for which that correlator is prewired. Stored values of prior path cumulative correlations (state metrics) are also applied to the adders. The adder outputs represent the cumulative correlations for each of the two paths by which the state may be left. A comparator is provided for each state for effecting a comparison of outputs of the two adders of that state. On the basis of the result of the comparison, one of the two outputs is selected as the survivor path and becomes the updated state metric for use in the next cycle for the adders of that state.
The outputs of the four state comparators are furnished as trellis connection data. Further, a four-input comparator receives and compares the cumulative correlations of the four survivor paths to select the survivor path having the highest cumulative to be the sole survivor.
By way of introduction to the invention to be detailed below, certain commonality in function with that above discussed is involved. Thus, a function of controlled encoding with a preselected convolutional code is employed, as in the '360 patent. A function of branch metric calculations is likewise involved and practiced on each interval of received data. An add, compare and select is also performed by the use of current branch metrics and prior state metrics. As will be seen, however, applicants implement this latter practice in parallel fashion, providing a plurality of add, compare and select circuit elements, each of which furnishes a survivor path selection or decision output. To place this distinction in perspective, it will be helpful to consider what use is made in the '360 patent of the four state comparator output information (which is termed trellis connection data as above noted) and of the sole survivor .oath indication or decision output.
In the '360 patent arrangement, the trellis connection data and sole survivor path indication are passed on seriatim as transmitted digits are received to a switch matrix decoder, a version thereof being seen in FIG. 7 of the '360 patent.
The implementation of the '360 patent switch matrix decoder involves an upper section having a plurality of shift registers, each receiving one of the trellis connection data, i.e., four shift registers. The switch matrix decoder has a lower section having a plurality of switch sets in number corresponding to the number of stages of the shift registers. Each switch set has individual switches corresponding in number to the number of states, i.e., four switches. The states of the switches in each switch set are controlled by the corresponding shift register stage in the upper section of the switch matrix decoder. The sole survivor path indication is connected to the first switch set in the succession and the last switch set in the succession converges on an output gate which furnishes the decoded output bit.
Assuming a steady-state to be at hand, i.e., the shift registers are full of trellis connection data, and a further set of trellis connection data and a further sole survivor path indication to be applied to the switch matrix decoder, the practice of the '360 patent is now to shift in the further trellis connection data and to have all switches set correspondingly to the contents of their counterpart register stages. A trellis path is accordingly established and a tracing back through such path occurs to obtain the decoded output bit.
The '360 approach may thus be characterized as implementing a path memory by using trellis connection data and sole survivor path indications obtained from an add, compare and select unit in conjunction with a hardwired representation of the convolutional encoder's trellis structure and by tracing back through the trellis to determine the correct databit to output.
Accepting that the relays of the '360 patent are high-speed solid-state switches, some delay attends the set-up of the switches upon such further input to the shift registers, i.e., what might be termed a unit of delay. However, there is also present a propagation delay through the switch matrix decoder in tracing back through the survivor trellis path giving rise to the output data.
It is to be recognized that decoder performance is improved as trellis path length is increased. However, in the prior art approach, as in the '360 patent, such improved performance by increase of trellis path length is attended by increased propagation delay through the switch matrix decoder. As a general rule, trellis path length L is desirably more than five or six times the "constraint length" (K) for desired system performance, constraint length being equal to the number of stages in the shift register of the system convolutional encoder. For a constraint length of seven, L is thus desirably forty or more. If each propagation per stage of the trellis path length is one unit of delay, the composite delay for the decoder example under discussion, is forty-one units of delay.
FIG. 2 depicts generally what is seen as the prior art convolutional decoder 110 addressed by the invention. Output data is provided on line 112 responsively to input data on line 114.
Data on line 114 is applied by line 116 to metrics computer 118. Branch metric indication furnished over line 120 to state metrics computer 122. The connection data and signals regarding survivor path indication per branch interval are applied respectively over lines 124 and 126 to switch matrix decoder 128. Decoded bits are applied seriatim on line 130 to output line 112. Delay 132 is experienced through switch matrix decoder 128, the delay corresponding to the above-discussed unit delay for setting up the switches of decoder 128 and the propagation delay attending tracing back through the trellis.
From applicants' viewpoint, the '360 patent convolutional decoder does not meet industry desires for lessened delay and, more particularly, a desire for increased trellis path length without attendant propagation delay.